package com.leetcode.题库;

import com.leetcode.common.model.ListNode;

/**
 * @author 覃国强
 * @date 2022-03-23 20:06
 */
public class 题库_0234_回文链表 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    ListNode listNode = ListNode.getForArray(new int[]{8,0,7,1,7,7,9,7,5,2,9,1,7,3,7,0,6,5,1,7,7,9,3,8,1,5,7,7,8,4,0,9,3,7,3,4,5,7,4,8,8,5,8,9,8,5,8,8,4,7,5,4,3,7,3,9,0,4,8,7,7,5,1,8,3,9,7,7,1,5,6,0,7,3,7,1,9,2,5,7,9,7,7,1,7,0,8});
    boolean palindrome = solution.isPalindrome(listNode.next);
    System.out.println(palindrome);
  }

  static
  class Solution {
    public boolean isPalindrome(ListNode head) {
      if (head == null || head.next == null) {
        return true;
      }
      if (head.next.next == null) {
        return head.val == head.next.val;
      }
      ListNode slow = head;
      ListNode fast = head;
      while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
      }
      ListNode tailHead = reverseList(slow.next);
      boolean answer = true;
      ListNode pointA = head;
      ListNode pointB = tailHead;
      while (pointA != null && pointB != null) {
        if (pointA.val != pointB.val) {
          answer = false;
          break;
        }
        pointA = pointA.next;
        pointB = pointB.next;
      }
      reverseList(tailHead);
      return answer;
    }

    private ListNode reverseList(ListNode head) {
      ListNode prev = null;
      ListNode node = head;
      ListNode next;
      while (node != null) {
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }
      return prev;
    }
  }

}
